Chapter 5. Grover’s Search Algorithm

Shor’s algorithm in Chapter 4 demonstrated exponential speedup on structured problems with ‘periodicity’. But what if the problem has no special structure like ‘periodicity’?

Looking up a phone number by name in a phone book is fast (structured search). However, finding a name by phone number requires checking each entry one by one from start to finish (unstructured search). Classically, searching an unstructured database with \(N\) items requires an average of \(N/2\) checks, and in the worst case, \(N\) checks.

In 1996, Lov Grover showed that a quantum computer can solve this unstructured search problem with only \(O(\sqrt{N})\) oracle calls. This is not exponential speedup, but a powerful quadratic speedup that changes \(O(N)\) to \(O(\sqrt{N})\) (10 billion vs 1 million) when \(N\) is very large (e.g., \(N=10^{10}\)).

The core principle of this algorithm is amplitude amplification, which amplifies the amplitude of the ‘correct’ state.

1. Fundamental Concepts

Unstructured Search Problem: There is a black box (oracle) containing \(N=2^n\) items. Among them, exactly one item (\(w\)) is the ‘marked’ item. We need to find this \(w\).
- Oracle Function: \(f(x)\) is 1 when \(x=w\) and 0 when \(x \neq w\).
Grover Oracle (\(U_w\)): Like the Deutsch algorithm in Chapter 2, the oracle does not directly reveal the answer but marks it using ‘phase kickback’. \[U_w |x\rangle = (-1)^{f(x)} |x\rangle\]
- Action: The oracle flips the phase of only the ‘marked’ item \(|w\rangle\) to \(-1\), leaving all other items unchanged.
  - \(|w\rangle \quad \xrightarrow{U_w} \quad -|w\rangle\)
  - \(|x\rangle \quad \xrightarrow{U_w} \quad |x\rangle \quad (\text{if } x \neq w)\)
- Geometrically, this operation reflects all vectors about the hyperplane perpendicular to \(|w\rangle\).
Amplitude Amplification: The core strategy of Grover’s algorithm.
1. Start: Begin with a uniform superposition state \(|s\rangle\) where all \(N\) items have equal amplitude \(1/\sqrt{N}\), achieved using the \(H\) gate.
2. Inversion: Apply the oracle \(U_w\) to flip the amplitude of the correct answer \(|w\rangle\) to \(-1/\sqrt{N}\).
3. Amplification: Apply the Grover diffusion operator (\(U_s\)) to invert all amplitudes about the mean (\(\mu\)).
4. Result: The amplitude of \(|w\rangle\), which was negative, rises significantly above the mean, while the amplitudes of the other items, which were positive, decrease slightly.
5. Repeat this process \(O(\sqrt{N})\) times.
Grover Diffusion Operator (\(U_s\)): An operator that performs ‘inversion about the mean’. \(U_s = 2|s\rangle\langle s| - \mathbf{1}\)
\(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}\) (uniform superposition state)
- \(U_s\) transforms all amplitudes \(a_i\) to \(a_i \to 2\mu - a_i\) (where \(\mu = \frac{1}{N}\sum_i a_i\)).

2. Symbols and Core Relations

Grover Iterate \(G\): The core iteration step of the algorithm is the successive application of the oracle and diffusion operator. \[G = U_s U_w\]
Core State Definitions: The entire algorithm can be perfectly described as a rotation occurring in a 2D plane. The two axes composing this plane are as follows.
- ‘Answer’ state (marked state): \(|w\rangle\)
- ‘Unanswered’ states (unmarked states): \(|\alpha\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq w} |x\rangle\)
- Starting state (uniform state): \(|s\rangle = \frac{1}{\sqrt{N}}\sum_{x} |x\rangle = \sqrt{\frac{N-1}{N}}|\alpha\rangle + \sqrt{\frac{1}{N}}|w\rangle\)
Geometrical Interpretation:
- \(|s\rangle = \cos(\theta)|\alpha\rangle + \sin(\theta)|w\rangle \quad\) (where \(\sin(\theta) = 1/\sqrt{N}\))
- \(\theta\) is the initial angle between \(|s\rangle\) and the ‘unanswered’ axis \(|\alpha\rangle\), and is very small when \(N\) is large.
- \(U_w\) = Reflection about the \(|\alpha\rangle\) axis
- \(U_s\) = Reflection about the \(|s\rangle\) axis
- \(G = U_s U_w\): Two reflections are equivalent to a rotation. \(G\) rotates the state vector by \(2\theta\) toward \(|w\rangle\).
Optimal Number of Iterations (\(k\)): Starting from the initial angle \(\theta\), to get as close as possible to the ‘answer’ axis \(|w\rangle\) (angle \(90^\circ = \pi/2\)),
\(k(2\theta) \approx \pi/2 \implies k \approx \frac{\pi}{4\theta}\)
When \(N\) is very large, \(\sin(\theta) \approx \theta \approx 1/\sqrt{N}\), so
\[k \approx \frac{\pi}{4}\sqrt{N}\]

3. Examples with Deeper Insight

Example 1: N=4 (n=2) - One Iteration

Problem: Among \(N=4\) (\(|00\rangle, |01\rangle, |10\rangle, |11\rangle\)), \(|11\rangle\) is the answer (\(w\)).
- Optimal number of times: \(k \approx \frac{\pi}{4}\sqrt{4} = \pi/2 \approx 1.57\). Therefore, \(k=1\) (only one repetition) is optimal.
- Computation (Step-by-step):
  1. Initial \(|s\rangle\): (All amplitudes \(1/2\))
    \(|s\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\)
  2. Oracle \(U_w\): Flips the phase of \(|11\rangle\) only.
    \(|\psi_1\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)\)
  3. Diffusion \(U_s\) (Mean inversion):
    - Mean calculation: \(\mu = \frac{1}{4} (1/2 + 1/2 + 1/2 - 1/2) = \frac{1}{4}(1) = 1/4\).
    - Inversion (\(a_i \to 2\mu - a_i\)):
      - \(|00\rangle\): \(2(1/4) - (1/2) = 0\)
      - \(|01\rangle\): \(2(1/4) - (1/2) = 0\)
      - \(|10\rangle\): \(2(1/4) - (1/2) = 0\)
      - \(|11\rangle\): \(2(1/4) - (-1/2) = 1/2 + 1/2 = 1\)
  4. Final state \(|\psi_2\rangle\):
    \(|\psi_2\rangle = 0|00\rangle + 0|01\rangle + 0|10\rangle + 1|11\rangle = |11\rangle\)
- 💡 Detailed explanation (100% probability):
  > With only one repetition (\(G\)), the initially uniform probability (\(P_i=25\%\)) across all items was amplified to 100% for the correct answer \(|11\rangle\). Measurement always yields \(|11\rangle\). For \(N=4\), the classical search requiring an average of 2.25 times (\(N/2 + ...\)) was completed in just one repetition.

Example 2: Geometric Interpretation (N=4)

Situation: Let’s interpret Example 1 as a 2D rotation.
- Axis Definition:
  - \(|w\rangle = |11\rangle\)
  - \(|\alpha\rangle = \frac{1}{\sqrt{3}}(|00\rangle + |01\rangle + |10\rangle)\) (wrong axis)
- Angle Calculation:
  - \(|s\rangle = \sqrt{\frac{3}{4}}|\alpha\rangle + \sqrt{\frac{1}{4}}|w\rangle = \cos(\theta)|\alpha\rangle + \sin(\theta)|w\rangle\)
  - \(\sin(\theta) = 1/\sqrt{4} = 1/2 \implies \theta = 30^\circ\) (\(\pi/6\)).
- Rotation:
  1. Start: The state vector is at \(|s\rangle\), which is \(\theta=30^\circ\) away from the \(|\alpha\rangle\) axis.
  2. \(U_w\) (Oracle): Reflects about the \(|\alpha\rangle\) axis (\(x\)-axis). The angle becomes \(-\theta = -30^\circ\).
  3. \(U_s\) (Diffusion): Reflects about the \(|s\rangle\) axis (original \(30^\circ\) axis).
  4. Final Angle: New angle = (axis angle) + (axis angle - current angle) \(= 30^\circ + (30^\circ - (-30^\circ)) = 30^\circ + 60^\circ = 90^\circ\).
- 💡 Detailed Explanation:
  
  The final angle is \(90^\circ\). \(90^\circ\) is perpendicular to the \(|\alpha\rangle\) axis, which is the same as the \(|w\rangle\) axis. We have geometrically confirmed that the state vector has rotated exactly to \(|w\rangle\). This example clearly shows that Grover’s two operators \(U_w\) and \(U_s\) act as a rotation operator \(G\) that rotates the state vector by \(2\theta\) within the 2D plane formed by \(|\alpha\rangle\) and \(|w\rangle\).

Example 3: Over-Iteration (Too Much Repetition)

Question: If we need to repeat approximately \(k \approx \frac{\pi}{4}\sqrt{N}\) times, wouldn’t repeating \(2k\) times be better?
Answer: No. You would overshoot the correct answer.
Situation: For \(N=4\) (Example 1), \(k=1\) was optimal (\(90^\circ\)). What happens if we repeat \(k=2\) times?
1. After \(k=1\), the state: \(|11\rangle\) (angle \(90^\circ\))
2. Applying \(U_w\): \(U_w|11\rangle = -|11\rangle\) (angle \(-90^\circ\) or \(270^\circ\))
3. Applying \(U_s\): \(|11\rangle\) must be expressed again as a linear combination of \(|\alpha\rangle\) and \(|s\rangle\)…
Geometric Interpretation (Easier Understanding):
When repeating \(k=1\) times, the rotation is \(2\theta = 60^\circ\), moving from \(30^\circ \to 90^\circ\).
When repeating \(k=2\) times, an additional \(2\theta = 60^\circ\) rotation occurs, moving from \(90^\circ \to 150^\circ\).
When repeating \(k=3\) times, another \(2\theta = 60^\circ\) rotation occurs, moving from \(150^\circ \to 210^\circ\) (\(-\theta = -30^\circ\) is nearly equivalent).
💡 Detailed Explanation:
> After 2 repetitions (\(150^\circ\)), the state vector has deviated by \(60^\circ\) from the \(|w\rangle\) axis (\(90^\circ\)). Measuring at this point gives a probability \(P(w) = \sin^2(150^\circ) = (1/2)^2 = 25\%\), which is the same as the initial state (\(25\%\))!
> After 3 repetitions (\(210^\circ\)), \(P(w) = \sin^2(210^\circ) = (-1/2)^2 = 25\%\).
> Grover’s algorithm is a delicate algorithm that must stop when it reaches the correct answer. To determine the optimal number of repetitions, you must know \(N\) (the total number of items) in advance.

4. Practice Problems

Diffusion Operator Construction: Explain how to implement the operator \(U_s = 2|s\rangle\langle s| - \mathbf{1}\) as a quantum circuit using \(H, X, Z\) gates by utilizing the identity \(U_s = H^{\otimes n} (2|0\rangle\langle 0| - \mathbf{1}) H^{\otimes n}\).
Optimal Repetition Count: Approximately how many times must Grover’s algorithm be repeated to find the answer in a database with \(N=1,000,000\) items? Compare this with the classical method.
Multiple Solutions (Multiple Items): If \(M\) out of \(N\) items are ‘correct’, what is the square of the amplitude (probability) of the subspace corresponding to the correct states (instead of \(|w\rangle\), the ‘correct subspace’) from the initial state \(|s\rangle\)?
\(N=2\) Search: Calculate what happens when Grover’s algorithm is executed once on an \(N=2\) system (\(|0\rangle, |1\rangle\)) to find \(|1\rangle\). (Hint: What is \(\theta\)?)
Shor vs Grover: Compare and explain the speedup (exponential vs quadratic) and the types of problems solved (structured vs unstructured) between Shor’s algorithm and Grover’s algorithm.

5. Solutions

\(U_s = H^{\otimes n} (2|0\rangle\langle 0| - \mathbf{1}) H^{\otimes n}\) is.
- \(H^{\otimes n}\) (Hadamard) transforms \(|s\rangle\) into \(|0\rangle^{\otimes n}\).
- \((2|0\rangle\langle 0| - \mathbf{1})\) operator leaves the \(|0\rangle\) state unchanged and flips the phase of all other states (\(|x\rangle \neq |0\rangle\)) orthogonal to \(|0\rangle\) to -1. (This can be implemented using a combination of a C…CZ gate with \(n-1\) control qubits controlling a Z gate and an X gate.)
- Applying \(H^{\otimes n}\) (Hadamard) again reverts \(|0\rangle^{\otimes n}\) back to \(|s\rangle\).
- As a result, this entire operation performs a reflection about the \(|s\rangle\) state.
Classical: Average \(N/2 = 500,000\) times. Worst \(N = 1,000,000\) times. Quantum: \(k \approx \frac{\pi}{4}\sqrt{N} = \frac{\pi}{4}\sqrt{1,000,000} = \frac{\pi}{4}(1000) \approx 785\) times. Approximately 785 times is sufficient, which is more than 600 times faster than the classical average.
\(|s\rangle = \frac{1}{\sqrt{N}}\sum |x\rangle\). Since there are \(M\) answers, the total amplitude squared (probability) in the answer subspace from \(|s\rangle\) is \(M \times |1/\sqrt{N}|^2 = M/N\). (That is, \(\sin^2(\theta) = M/N\))
\(N=2\). \(\sin(\theta) = 1/\sqrt{2} \implies \theta = 45^\circ\) (\(\pi/4\)). Rotation angle \(2\theta = 90^\circ\) (\(\pi/2\)). Rotating from the initial angle \(\theta=45^\circ\) by \(90^\circ\) results in the final angle \(135^\circ\). \(P(w) = \sin^2(135^\circ) = (1/\sqrt{2})^2 = 1/2\). Starting from an initial probability of 50%, it remains at 50%, so there is no amplification. Grover’s algorithm does not provide an advantage for \(N=2\).
Shor: Solves the structural problem of ‘period finding’. Provides exponential speedup from \(O(e^n) \to O(n^3)\). Grover: Solves the unstructured search problem. Provides quadratic speedup from \(O(N) \to O(\sqrt{N})\) (i.e., \(O(2^n) \to O(2^{n/2})\)).